package class03;

import java.util.ArrayList;
//树形dp 时间复杂度O(n)
public class Code12_MaxSubBSTSize {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            val = value;
        }
    }

    public static class Info {
        /**
         * isBST 可以做调整
         * 如果搜索二叉树节点和树的节点树相等，说明，树一定是搜索二叉树
         */
        // boolean isBST;
        public int maxBSTSubtreeSize;
        public int allSize;
        int max;
        int min;

        Info(int maxBSTSubtreeSize, int allSize, int max, int min) {
            this.maxBSTSubtreeSize = maxBSTSubtreeSize;
            this.allSize = allSize;
            this.max = max;
            this.min = min;

        }
    }

    public static int largestBSTSubtree(TreeNode head) {
        if (head == null) {
            return 0;
        }
        return process(head).maxBSTSubtreeSize;
    }

    static Info process(TreeNode node) {
        if (null == node) {
            return null;
        }

        /**
         * 1如果node 不参与
         * 1.1 左子树完全二叉树的个数
         * 1.2 右子树完全二叉树个数
         * 1.3 max
         * 2 node 参与
         * 2.1 左右子树都是完全二叉树
         * 2.2 左右子树的max 相加 +1
         */


        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);


        int maxBSTSubtreeSize = 0;
        int max = node.val;
        int min = node.val;
        int allSize = 1;

        if (null != leftInfo) {
            allSize += leftInfo.allSize;
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);

        }
        if (null != rightInfo) {
            allSize += rightInfo.allSize;
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);

        }
        boolean leftIsBST = leftInfo == null || leftInfo.maxBSTSubtreeSize == leftInfo.allSize;
        boolean rightIsBST = rightInfo == null || rightInfo.maxBSTSubtreeSize == rightInfo.allSize;

        int p3 = -1;
        if (leftIsBST && rightIsBST) {
            boolean leftMaxLessX = leftInfo == null || leftInfo.max < node.val;
            boolean rightMinMoreX = rightInfo == null || rightInfo.min > node.val;


            if (leftMaxLessX && rightMinMoreX) {
                p3 = (leftInfo == null ? 0 : leftInfo.maxBSTSubtreeSize) + (rightInfo == null ? 0 : rightInfo.maxBSTSubtreeSize) + 1;
            }
        }


        int p1 = -1;
        int p2 = -1;
        if (null != leftInfo) {
            p1 = leftInfo.maxBSTSubtreeSize;


        }
        if (null != rightInfo) {

            p2 = rightInfo.maxBSTSubtreeSize;

        }


        return new Info(Math.max(Math.max(p2, p1), p3), allSize, max, min);


    }


    // 为了验证
    // 对数器方法
    public static TreeNode generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // 为了验证
    // 对数器方法
    public static TreeNode generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        TreeNode head = new TreeNode((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    // 为了验证
    // 对数器方法
    public static int right(TreeNode head) {
        if (head == null) {
            return 0;
        }
        int h = getBSTSize(head);
        if (h != 0) {
            return h;
        }
        return Math.max(right(head.left), right(head.right));
    }

    // 为了验证
    // 对数器方法
    public static int getBSTSize(TreeNode head) {
        if (head == null) {
            return 0;
        }
        ArrayList<TreeNode> arr = new ArrayList<>();
        in(head, arr);
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i).val <= arr.get(i - 1).val) {
                return 0;
            }
        }
        return arr.size();
    }

    // 为了验证
    // 对数器方法
    public static void in(TreeNode head, ArrayList<TreeNode> arr) {
        if (head == null) {
            return;
        }
        in(head.left, arr);
        arr.add(head);
        in(head.right, arr);
    }

    public static void main(String[] args) {
        int maxLevel = 4;
        int maxValue = 100;
        int testTimes = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            TreeNode head = generateRandomBST(maxLevel, maxValue);
            if (largestBSTSubtree(head) != right(head)) {
                System.out.println("出错了！");
            }
        }
        System.out.println("测试结束");

    }
}
